% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass{llncs}
\usepackage{graphicx}
\usepackage{polyglossia}
\usepackage{amsmath,amsfonts}
\usepackage{xltxtra}
\usepackage{ulem}
\usepackage{hyperref}
\usepackage{tabularx}
\usepackage{ifthen}
\usepackage{wrapfig}
\usepackage{listings}
\usepackage{enumitem}
\usepackage{pseudocode}
\usepackage{algorithm}
\usepackage{algorithmicx}
\floatname{algorithm}{Algorithmus} 
\usepackage{algpseudocode}
\usepackage{subfig}
\usepackage{lscape}
\usepackage{rotating}
\usepackage{tikz}
\usepackage[usenames,dvipsnames]{pstricks}
\usepackage{epsfig}
\usepackage{pst-grad} % For gradients
\usepackage{pst-plot} % For axes


\pgfdeclarelayer{bg}    % declare background layer
\pgfsetlayers{bg,main}  % set the order of the layers (main is the standard layer)

\setmainlanguage[spelling=new, latesthyphen=true]{german}
\hypersetup{pdfborder=0 0 0}

\begin{document}

\pagestyle{headings}  % switches on printing of running heads
%
\title{Ameisenintelligenz: Konzept und Anwendung}
%
\titlerunning{Ameisenintelligenz}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Jean-Bernard Wansi Njengoue (\href{mailto:wansj1@bfh.ch}{\email{wansj1@bfh.ch}}) und Manuel Frischknecht (\href{mailto:frism1@bfh.ch}{\email{frism1@bfh.ch}})}
%
\authorrunning{J-B. Wansi, M. Frischknecht}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Jean-Bernard Wansi, Manuel Frischknecht}
%
\institute{BFH-TI, Quellgasse 21, CH-2501 Biel}

\maketitle              % typeset the title of the contribution

\begin{abstract}
Ziel dieser Arbeit ist es, einen Einstieg in die Grundlagen der Ameisenintelligenz zu vermitteln und dabei die Grundzüge der ersten Algorithmen auf diesem Gebiet zu erläutern.
Ausserdem werden als Beispiel einer Anwendung dieser Algorithmengruppe Lösungsansätze auf der Basis der \textbf{Ant System}, \textbf{Ant Colony System} und 
\textbf{Ant-Q} Algorithmen auf das \textbf{Traveling Salesman Problem} präsentiert und erläutert. 
Ameisenalgorithmen sind heuristische Verfahren in der Optimierung und basieren auf dem Prinzip, nach dem Ameisen mit Hilfe von Duftstoffen (Pheromonen) 
den direktesten Weg von ihren Ameisenhügel zu einer Futterquelle finden.
\end{abstract}
%

\section{Allgemeines zur Ameisenintelligenz}
\subsection{Einleitung}

Ameisenintelligenz ist ein Konzept, das in der Optimierung zur Lösung von Entscheidungsproblemen benutzt werden kann. Es handelt sich dabei um ein heuristisches Verfahren, 
d.h. das Ziel besteht nicht darin, für ein Entscheidungsproblem die optimale Lösung zu finden. Stattdessen wird versucht, in angemessener Zeit eine möglichst gute Lösung zu konstruieren,
weshalb eine von einem solchen Algorithmus gefundene Lösung stets schlechter als die optimale Lösung sein kann. Sollte ein Ameisenalgorithmus tatsächlich die bestmögliche Löung für ein
Problem finden, lässt sich dies ausserdem nicht aus dem bekannten Kontext belegen.

Das Konzept der Ameisenintelligenz basiert auf der Art, wie Ameisen den kürzesten Weg von ihrem Ameisenhaufen zu einer Futterquelle und wieder zurück ermitteln: 
Diese Insekten kommunizieren untereinander über Duftstoffe (\textit{Pheromone}), die sie unterwegs hinterlassen und die den von ihnen zurückgelegten Weg markieren. 
Auf ihrer Suche nach Futter werden andere Ameisen von bestehenden Pheromonbahnen beeinflusst und wenden sich am ehesten jenen Wegen zu, auf denen ein höherer Pheromongehalt vorhanden ist.

Damit basiert das Konzept auf der \textbf{Stigmergie}, einer von Pierre-Paul Grassé (* 27.11.1895 Périgueux; † 9.7.1985) geprägten Theorie. Grassé benutzte den Begriff bereits im Jahr 1959, 
als er das Verhalten von Termiten beim Nestbau beschrieb. Im allgemeinen steht Stigmergie für die Kommunikation zwischen vielen Individuen, indem diese ihr unmittelbare Umfeld beeinflussen.

Im Jahr 1991 entwickelte Marco Dorigo \textbf{Ant System}, den ersten Ameisenalgorithmus im Rahmen seiner Doktorarbeit. 
Ein technischer Artikel von Dorigo und einigen Kollegen zu diesem Algorithmus wurde fünf Jahre später veröffentlicht\cite{bib:antsystem}.
Weitere zwei Jahre später wurde eine weitere Arbeit von Dorigo, diesmal unter Mithilfe von Luca Maria Gambardella, veröffentlicht, in dem \textbf{Ant Colony System}, 
eine Weiterentwicklung des ersten Algorithmus, vorgestellt wurde\cite{bib:antcolonysystem}. 

\subsection{Grundlagen}

Die Grundidee der Ameisenintelligenz lässt sich an der Situation in Abbildung~\ref{fig:ants} veranschaulichen:

\begin{figure}[h!]
\begin{center}$
\begin{array}{ccc}
\includegraphics[width=0.33\textwidth]{ants1.png} &
\includegraphics[width=0.33\textwidth]{ants2.png} &
\includegraphics[width=0.33\textwidth]{ants3.png}
\end{array}$
\end{center}
\caption{Ameisen auf Futtersuche kommunizieren indirekt über Pheromonspuren, die sie auf ihren Bahnen hinterlassen.}
\label{fig:ants}
\end{figure}

Auf dem Weg zwischen dem Nest der Ameisen und der Futterquelle liegt ein Hindernis, wobei der linke Weg um das Hindernis herum leicht länger ist als der rechte. 
Zu Beginn entscheiden die Ameisen zufällig zwischen beiden Routen, da auf beiden Wegen bisher noch kein Pheromon liegt (siehe linkes Bild). 
Da der rechte Weg jedoch kürzer ist, werden die ersten Ameisen, die ihr Futter bei der Futterquelle abholen, schneller zurück im Nest sein und sowohl auf dem Hin- als auch auf 
dem Rückweg ihr Pheromon verteilt haben, weshalb der rechte Weg nun mehr Duftstoffe aufweist als der linke (mittleres Bild). Dies bewegt mehr Ameisen aus dem Nest dazu, sich
für den rechten Weg zu entscheiden, was wiederum dazu führt, dass auf der rechten Seite des Hindernisses noch mehr Pheromone liegen. 
Schliesslich wird sich ein Grossteil der Ameisen für den direkteren Weg zur Nahrung entscheiden (rechtes Bild).

\subsection{Modellierung}

Um diese Art des "kollektiven Gedächnisses" in der Programmierung zu nutzen, stelle man sich die obige Situation als Teil eines Entscheidungsproblems vor: 
Wir definieren die Punkte A,B,C,D,E und F. Mehrere Agenten, die unsere Ameisen darstellen, suchen nach dem kürzesten Weg von A nach F. 
Ausserdem definieren wir für jede Kante des Graphen einen Pheromon-Wert $\tau = 0$.

\begin{figure}[htbp]
\subfloat[]{
\begin{tikzpicture}
\node (d) at (0,1.5) {$D$};
\node (e) at (-2,0) {$E$} edge[-]node[above left, xshift=-2em]{$d=1$} (d);
\node (c) at (1,0) {$C$} edge[-] node[above right, xshift=1em]{$d=0.5$}(d);
\node (b) at (0,-1.5) {$B$} edge[-]node[above right, xshift=1em]{$d=0.5$}(c)
			  edge[-]node[above left, xshift=-2em]{$d=1$}(e);
\node (f) at (0,3) {$F$} edge[-](d);
\node (a) at (0,-3) {$A$} edge[-](b);
\label{fig:(a)}
\end{tikzpicture}}
\qquad
\subfloat[]{
\fbox{$t=0$}
\begin{tikzpicture}

\node (d) at (0,1.5) {$D$};
\node (e) at (-2,0) {$E$} edge[-]node[above left]{$15\:Ameisen$} (d);
\node (c) at (1,0) {$C$} edge[-] node[above right]{$15\:Ameisen$}(d);
\node (b) at (0,-1.5) {$B$} edge[-]node[above right,yshift=-1em]{$15\:Ameisen$}(c)
			  edge[-]node[above left,yshift=-1em]{$15\:Ameisen$}(e);
\node (f) at (0,3) {$F$} edge[-]node[above right]{$30\:Ameisen$}(d);
\node (a) at (0,-3) {$A$} edge[-]node[above right]{$30\:Ameisen$}(b);

%\path (a) edge [->] (b)
 %(b) edge [->] (c)
 %(b) edge [->] (h)
 %(d) edge [->] (h)
 %(d) edge [->] (c)
(%e) edge [->] (d);
\label{fig:(b)}
\end{tikzpicture}}
\qquad
\subfloat[]{
\fbox{$t=1$}
\begin{tikzpicture}

\node (d) at (0,1.5) {$D$};
\node (e) at (-2,0) {$E$} edge[-]node[above left]{$10\:Ameisen$}node[above right,xshift=-5em,yshift=-3mm]{$\tau=15$} (d);
\node (c) at (1,0) {$C$} edge[-] node[above right]{$20\:Ameisen$}node[below left,xshift=5em,yshift=1mm]{$\tau=30$}(d);
\node (b) at (0,-1.5) {$B$} edge[-]node[above right,yshift=-1em]{$20\:Ameisen$}node[below left,xshift=5em,yshift=5mm]{$\tau=30$}(c)
			  edge[-]node[above left,yshift=-1em]{$10\:Ameisen$}node[above right,xshift=-6em,yshift=1mm]{$\tau=15$}(e);
\node (f) at (0,3) {$F$} edge[-]node[above right]{$30\:Ameisen$}(d);
\node (a) at (0,-3) {$A$} edge[-]node[above right]{$30\:Ameisen$}(b);

%\path (0.25,-3) edge [->] (0.25,-2);
%(b) edge [->] (c)
%(b) edge [->] (h)
%(d) edge [->] (h)
%(d) edge [->] (c)
%(e) edge [->] (d);
\label{fig:(c)}
\end{tikzpicture}}
\qquad
\caption{Modellierung der selben Situation als Entscheidungsproblem}
\begin{enumerate}[label=\emph{\alph*})]
	\item Der Graph mit eingetragenen Distanzen
	\item Noch ist auf keiner der Kanten Pheromon vorhanden. Die Ameisen, die von beiden Seiten auf das Hindernis zu laufen, entscheiden sich zu gleichen Teilen für beide Wege.
	\item Nach der ersten Iteration liegt auf der kürzeren Kante mehr Pheromon, weshalb sie von mehr Ameisen benutzt wird.
\end{enumerate}
\end{figure}

Der Weg, der von Punkt B über Punkt E nach D führt, ist doppelt so lang wie jener über Punkt C. Die Suche nach dem kürzesten Weg gestaltet sich nun wie folgt: 
An beiden Enden werden jeweils 30 Agenten postiert, die gleichzeitig schrittweise nach einem Weg zum anderen Ende suchen. 
An den Punkten B und D muss sich jeder Einzelne von ihnen für eine Richtung entscheiden. 
Da bisher noch keine Informationen (in Form von Pheromonwerten) vorhanden sind, werden sich für beide Richtungen etwa gleich viele Agenten entscheiden. 
Nach dieser ersten Iteration werden die Pheromonwerte für jede Kante neu berechnet, wobei jeder Agent den Wert der Kanten erhöht, die er besucht hat.
Diese Differenz $\Delta\tau$ ist umgekehrt proportional zur Länge des Gesamtweges, den der Agent zurückgelegt hat:

$$
\Delta\tau = \frac{Q}{L_k}
$$
 
Diese simple Regel führt dazu, dass mit jeder Iteration der Pheromonwert derjenigen Kanten, die auf der kürzesten Route von A nach F liegen, besonders stark erhöht werden;
während späterer Iterationen muss nun noch dafür gesorgt werden, dass sich Agenten auch durch diese Pheromonwerte gegenseitig beeinflussen können. 
Dies wird erreicht, indem man dafür sorgt, dass die Wahrscheinlichkeit, mit der sich ein Agent an Punkt i für die Kante nach Punkt j entscheidet, proportional zum relativen Pheromonwert 
der Kante (verglichen mit allen in Frage kommenden Kanten) ist:

$$
p(i,j) = \frac{\tau(i,j)}{\sum{k \in J(i)}{\tau(i,k)}}
$$

\section{Anwendung auf das Traveling Salesman Problem}

\subsection{Grundlegendes über das Traveling Salesman Problem}

Das Traveling Salesman Problem (kurz \textbf{TSP}) ist ein Optimierungsproblem der Informatik. 
Die Problemstellung geht von einem Handelsreisenden aus, der im Rahmen einer Route eine gewisse Anzahl Städte besuchen muss.  
Ziel des Reisenden ist es, eine \textbf{optimale Route} zu erstellen, bei der alle Städte genau einmal besucht werden und gleichzeitig die zurückgelegte Distanz minimal ist.

Mathematisch wird das Problem oftmals über einen vollständigen gewichteten Graph beschrieben, dessen Knoten die Städte darstellen. 
Die Kanten zwischen den Knoten weisen dabei die Distanz von der einen Stadt zur nächsten auf. So betrachtet, stellt das TSP einen Spezialfall des \textbf{Hamiltonkreisproblems} dar.

\begin{figure}[h]
	\caption{Mögliche Graphendarstellung eines TSP}
	\centering
	\begin{tikzpicture}[x=0.09\linewidth]
		\node[draw,circle] at (1,1) (a) {a};
		\node[draw,circle] at (0,3) (b) {b};
		\node[draw,circle] at (2,5) (c) {c};
		\node[draw,circle] at (4,6) (d) {d};
		\node[draw,circle] at (6,3) (e) {e};
		\node[draw,circle] at (5,1) (f) {f};
		\node[draw,circle] at (3.75,3.5) (g) {g};
		
		\begin{pgfonlayer}{bg}
			\draw[red,-] (a) edge (b);
			\draw[black,-] (a) edge (c);
			\draw[black,-] (a) edge (d);
			\draw[black,-] (a) edge (e);
			\draw[red,-] (a) edge (f);
			\draw[black,-] (a) edge (g);
			\draw[red,-] (b) edge (c);
			\draw[black,-] (b) edge (d);
			\draw[black,-] (b) edge (e);
			\draw[black,-] (b) edge (f);
			\draw[black,-] (b) edge (g);
			\draw[red,-] (c) edge (d);
			\draw[black,-] (c) edge (e);
			\draw[black,-] (c) edge (f);
			\draw[black,-] (c) edge (g);
			\draw[black,-] (d) edge (e);
			\draw[black,-] (d) edge (f);
			\draw[red,-] (d) edge (g);
			\draw[red,-] (e) edge (f);
			\draw[red,-] (e) edge (g);
			\draw[black,-] (g) edge (f);
		\end{pgfonlayer}
	\end{tikzpicture}
\end{figure}

Das TSP wird zur Menge der NP-Schweren Probleme gezählt; der Zeitaufwand von Algorithmen, die eine nachweislich optimale Lösung berechnen, 
wächst mit zunehmender Anzahl an Städten exponentiell an, weshalb das Problem auch sehr oft durch metaheuristische Verfahren, unter anderem auch 
Ameisenintelligenz, behandelt wird. Wichtig ist hierbei, dass das Ziel dieser Algorithmen nicht die optimale Lösung, sondern die Verbesserung 
einer bestehenden Lösung ist. Dies bedeutet, dass Ameisenintelligenz-Algorithmen zwar nach einer gewissen Zeit eine gute Lösung liefern, diese 
jedoch immer beliebig schlechter als die \textbf{optimale} Lösung ausfallen kann.

\subsection{Anwendung von Ant System auf das TSP}

\subsubsection{Modellierung des Problems}

Im Fall von \textbf{AS} wird das \textbf{TSP} als eine Menge $ V = \{ a,b,..\} $ von Städten abgebildet. 
Zu jedem Städtepaar $(i,j)$ in $V$ ist eine Distanz $\delta(i,j)$ definiert. 
Zusätzlich dazu wird als weitere Grösse $\tau(i,j)$ eingeführt, das dem Mass an Pheromon entspricht, das auf der Kante von i nach j vorhanden ist. 
Für symmetrische TSP (mit den selben Distanz in beide Richtungen jeder Kante) gilt hierbei: $\tau(i,j) = \tau(j,i)$

\subsubsection{Vorgehensweise}

Der AS-Algorithmus erstellt mehrere Agenten (“Ameisen”), die in einer Schleife simultan den Graph des TSP auf der Suche nach einer Lösung ablaufen. 

Eine Iteration des Algorithmus gliedert sich in zwei Phasen: 
\begin{enumerate}
	\item Die Berechnung von Routen durch die Agenten.
	\item Die Berechnung des Pheromongehalts aller Kanten.
\end{enumerate}

Diese Phasen lassen sich im Wesentlichen auf je eine Grundregel reduzieren, die das Verhalten der Agenten bestimmen:

\paragraph{Wahl der Kanten ("State Transition Rule"): }
Bei jedem Knoten $i$, den ein Agent besucht, entscheidet er durch Zufall, welche der verfügbaren Kanten er als nächstes benutzen wird, 
wobei die relativen Wahrscheinlichkeiten über die Länge der Kante und den darauf bereits vorhandenen Pheromongehalt definiert werden:

\begin{equation}
\label{eq:AS_StateTransitionRule}
p(i,j) = 
\begin{cases}
	{ \frac{\tau(i,j) ^ \alpha \times \eta(i,j) ^ \beta}{\underset{k \in V}{\sum} \tau(i,j) ^ \alpha \times \eta(i,j) ^ \beta} } & \mbox{wenn } j \in J \\
	0 & \text{andernfalls}
\end{cases}
\end{equation}

Hierbei ist $J$ die Menge der Städte, die von der Ameise noch nicht besucht wurden; der heuristische Wert $\eta$ entspricht $\frac{1}{\delta(i,j)}$, was dazu führt, 
dass kürzere Kanten längeren bevorzugt werden.

\paragraph{Update der Pheromonwerte ("Updating Rule"): }

Vor dem Verteilen von Pheromonen auf dem Graph wird $\tau$ zuerst für jede Kante um einen festgelegten Bruchteil reduziert. 
Dieses “Verdunsten” von Pheromonen führt dazu, dass regelmässig besuchte Kanten “beliebter” werden.
Das Mass an Pheromonen, die von einer bestimmten Ameise auf den Kanten ihrer letzen Route versprüht wird, 
verhält sich dabei umgekehrt proportional zur Länge der Route selbst. Daher verfügen nach mehreren Iterationen tendenziell die Kanten, 
die Teil von kurzen Routen sind, über mehr Pheromone.

Anschliessend werden die Pheromonwerte der zuvor von den Ameisen besuchten Kanten neu berechnet:

\begin{equation}
\label{nexttau}
\tau(i,j) = \rho \cdot \tau(i,j) + \sum_{k = 1}^{n}\Delta\tau_k(i,j)
\end{equation}

$\rho$ entspricht dabei dem "Verdunstungsgrad"; $\Delta\tau_k(i,j)$ ergibt sich aus der Pheromonmenge $Q$ pro Ameise und der Länge $L_k$ der von Ameise k gefundenen Route:

\begin{equation}
\label{deltatau}
\Delta\tau _k(i,j) = \frac{Q}{L_k}
\end{equation}

\subsubsection{Ablauf}

Der Ant System Algorithmus lässt sich grob in folgende Schritte unterteilen:

\begin{enumerate}
	\item Initialisierung aller Variabeln
	\item Durchführen der Iterationen (Hauptschleife)
	\begin{enumerate}[label*=\arabic*.]
		\item Schleife über alle Ameisen
			\begin{enumerate}[label*=\arabic*.]
				\item Schrittweise Berechnung der Tour der Ameise
				\item Berechnung des von der Ameise versprühten Pheromonwertes
				\item Update der besten gefundenen Lösung
			\end{enumerate}
		\item Berechnung der neuen Pheromonwerte
    \end{enumerate}
\end{enumerate}

\subsubsection{Zeitkomplexität}

Der komplexeste Teil jedes Ameisen-Tasks ist die Berechnung der Route, die eine Zeitkomplexität von $O(n^2)$ aufweist. Der gesamte Algorithmus skaliert also mit $O(i_{max} \cdot m \cdot n^2)$, wobei $i_{max}$ die
Anzahl der Iterationen und $m$ die Anzahl eingesetzter Agenten darstellen. In ihrer Arbeit weisen die Autoren auf einen linearen Zusammenhang zwischen der optimalen Anzahl Ameisen und der Anzahl Städte hin\cite{bib:antsystem},
weshalb sie von einer Laufzeit von $O(i_{max} \cdot n^3)$ ausgehen.

Die Tourensuche der einzelnen Ameisen lässt sich dabei parallelisieren. Eine mögliche Umsetzung (ohne Parallelisierung) 
kann dem Pseudocode in \textbf{Anhang~\ref{appendix:AS}} entnommen werden.

\subsection{Anwendung von Ant Colony System auf das TSP}

\subsubsection{Unterschiede zwischen Ant System und Ant Colony System}

Während das \textbf{Ant Colony System} zu weiten Teilen auf den selben Ideen beruht wie sein Vorgänger (\textbf{Ant System}), 
unterscheiden sich die beiden Algorithmen vor allem durch drei Punkte:

\begin{enumerate}
	\item Während die Ameisen in \textbf{Ant System} sich bei der Wahl der zu besuchenden Kanten lediglich durch die Gewichtung zwischen Heuristik und Pheromonen beeinflussen liessen,
			führt \textbf{Ant Colony System} einen weiteren Parameter ein, der ein erwünschtes Mass an "Erforschung" von zufälligen Kanten erlaubt.
	\item \textbf{ACS} führt zusätzlich zur bisherigen \textit{"globalen"} Update-Regel für die Pheromonwerte des Graphen eine \textit{"lokale"} Regel ein, die von den Ameisen bereits
			während der Konstruktion einer Tour angewandt wird.
	\item Die globale Update-Regel wird nur noch auf die Kanten der kürzesten Tour angewandt.
\end{enumerate}

\subsubsection{Vorgehensweise}

Wie schon sein Vorgänger, arbeitet auch \textbf{ACS} in Iterationen, die durch verschiedene Grundregeln bestimmt werden:

\paragraph{Wahl der Kanten ("State Transition Rule"): }
Während in \textbf{AS} die Entscheidung zwischen möglichen Kanten ausschliesslich auf einer Kombination aus Heuristik und akkumulierten Erfahrungswerten basiert, wird in \textbf{ACS} eine andere 
Vorgehensweise verwendet. Durch einen neuen Parameter $0 \leq q_0 \leq 1$ wird die Wahrscheinlichkeit definiert, mit der der Algorithmus an jedem Punkt die beste bekannte Kante wählt (die Definition der
\textit{"besten"} Kante ist dieselbe wie schon in \textbf{AS}); im anderen Fall wird mit der selben Wahrscheinlichkeit wie beim Vorgänger zwischen den einzelnen Kanten entschieden. 
Somit lässt sich zusätzlich zur Gewichtung von Heuristik- und Erfahrungswerten definieren, wie stark der Algorithmus mögliche Alternativen zu bisherigen Favoriten erforschen soll.

Die neue Regel zur Wahl der nächsten Stadt $s$, ausgehend von der aktuellen Position $r$, formuliert sich damit wie folgt:

\begin{equation}
	s = 
	\begin{cases}
		\underset{u \in J(r)}{max}\{\tau(r,u) ^ \alpha \times \eta(r,u) ^ \beta\} & \text{wenn } q \leq q_0 \\
		S & andernfalls
	\end{cases}
\end{equation}

Hierbei ist q eine gleichverteilte Zufallszahl im Bereich $[0\dots{}1]$. Im Fall $q > q_0$ fällt die Wahl der Stadt $S$ gemäss Gleichung~\eqref{eq:AS_StateTransitionRule} aus.

\paragraph{Update der Pheromonwerte nach jeder Iteration ("Global Updating Rule"): }
\textbf{ACS} beschreitet auch bei der Verteilung von Pheromonen auf die abgesuchten Strecken neue Wege. Die Berechnung der Pheromonwerte nach jeder Iteration beschränkt sich fast
ausschliesslich auf die Verdunstung; lediglich die Pheromonwerte jener Kanten, die Teil der bisher besten Tour (der gesamten Laufzeit) sind, werden verstärkt:

\begin{eqnarray}
\nonumber \tau(r,s) & \gets & (1-\rho_{global}) \cdot \tau(r.s) + \rho_{global} \cdot \Delta\tau(r,s) \\
\text{wobei gilt: }\Delta\tau(r,s) &  = &
	\begin{cases}
		(L_{min}) ^ {-1} & \text{falls }(r,s) \in \text{beste bisherige Lösung} \\
		0 & \text{andernfalls}
	\end{cases}
\end{eqnarray}

$L_{min}$ bezeichnet die Länge der besten Tour, die seit dem Start des Algorithmus gefunden wurde. In ihrer Arbeit weisen die Autoren von \textbf{ACS} ausserdem auf 
die Möglichkeit hin, die Kanten der besten Routen des aktuellen Schleifendurchlaufs anstelle jener der allgemein besten Lösung zu verstärken.
Experimente zeigten jedoch, dass diese Alternative keinen grossen Einfluss auf den Algorithmus zeigte und die entsprechenden Resultate allenfalls etwas schlechter
ausfielen \cite{bib:antcolonysystem}.

\paragraph{Update der Pheromonwerte während der Tourenbildung ("Local Updating Rule"): }
Zusätzlich zur Neuberechnung der Pheromonwerte pro Iteration führen die Autoren von \textbf{ACS} nun eine weitere Regel ein, die von den Agenten bereits während der
Konstruktion ihrer Lösungen auf die besuchten Kanten angewandt werden. Die Idee dieser Regel ist eine dynamischere Veränderung der Pheromonwerte, was verhindern soll, dass
sich die Ameisen beim Finden von neuen Touren immer auf die beste bereits bekannte Lösung beziehen. Die neue Update-Regel verringert den Pheromongehalt jeder Kante, die von 
einer Ameise besucht wird, und verringert somit die Wahrscheinlichkeit, dass eine andere Ameise genau die selbe Kante nochmals benutzt. Der neue Pheromonwert einer besuchten 
Kante berechnet sich wie folgt:

\begin{eqnarray}
\nonumber \tau(r,s) \gets (1-\rho_{lokal}) \cdot \tau(r,s) + \rho_{lokal} \cdot \Delta\tau(r,s)
\end{eqnarray}

Was $\Delta\tau(r,s)$ angeht, testeten die Autoren auch bei dieser Regel mehrere mögliche Variationen: Für den \textbf{ACS-Algorithmus} entschieden sie sich für 
$\Delta\tau(r,s) = \tau_0$, was in Experimenten zu guten Resultaten führte.
Eine andere Variante von \textbf{ACS} mit einer von Q-Learning inspirierten Formel ($\Delta\tau(r,s) = \gamma \cdot \underset{z \in J(r)}{max}\{\tau(s,z)\}$), \textbf{Ant-Q} getauft\cite{bib:antq}\cite{bib:antqprops}, 
führt gemäss dieser Experimente zu ähnlichen Resultaten\cite{bib:antcolonysystem}, benötigt aber mehr Rechenschritte.

\subsubsection{Ablauf}

Entsprechend seiner Definition weist Ablauf eines \textbf{ACS} oder \textbf{Ant-Q} Algorithmus ein paar zusätzliche Phasen auf:

\begin{enumerate}
	\item Initialisierung aller Variabeln
	\item Durchführen der Iterationen (Hauptschleife)
	\begin{enumerate}[label*=\arabic*.]
		\item Schleife über alle Ameisen
			\begin{enumerate}[label*=\arabic*.]
				\item Schrittweise Berechnung der Tour der Ameise
					\begin{enumerate}[label*=\arabic*.]
						\item Wahl der nächsten Stadt
						\item Update der Pheromonwerte für den aktuellen Schritt
					\end{enumerate}
					\item Update der besten gefundenen Lösung
			\end{enumerate}
		\item Verzögertes Update der Pheromonwerte und Verstärkung der kürzesten bisher gefundenen Route
    \end{enumerate}
\end{enumerate}

Die Tourensuche der einzelnen Ameisen lässt sich wiederum parallelisieren. Mögliche Umsetzungen befinden sich in den \textbf{Anhängen~\ref{appendix:ACS}~und~\ref{appendix:AQ}}. 

\subsection{Resultate der einzelnen Algorithmen}

Um die Entwicklung einer Lösung durch die erklärten Algorithmen zu veranschaulichen, haben wir sie einige Male mit fest definierten Parametern auf das selbe Problem angewandt. 
Als Problem verwendeten wir das \textbf{Oliver30} TSP (erstmals vorgeschlagen in \cite{bib:oliver}), das als "Benchmark" für TSP-Algorithmen eine bekannte Grösse ist.

Das Oliver30 ist ein symmetrisches TSP mit 30 durch Koordinaten festgelegten Städten, dessen Kantengewichte sich aus dem euklidischen Abstand zwischen den Städten ergeben. 
Die optimale Lösung dieses Problems ist bekannt ($L_{min} \approx 423.741$), weshalb man die Qualität einer Lösung direkt abschätzen kann. An den Grafiken lässt sich erkennen, dass 
Ameisenintelligenzalgorithmen schon unter 100 Iterationen (was bei 10 Ameisen 1000 berechneten Routen entspricht) sehr gute Lösungskandidaten finden können, während ein Problem von dieser Grösse 
über Brute Force-Ansätze nicht mehr zu lösen ist (30 Städte resultieren in $30! \approx 2.65 \cdot 10 ^{32}$ möglichen Routen).

Die hier gezeigten Grafiken sollen jedoch lediglich die typische Entwicklung einer Lösung durch Ameisenintelligenz-Algorithmen aufzeigen und sind nicht als Kennzahlen zu verstehen. 
Genauere statistische Informationen und Analysen der besten Parameter können in den Arbeiten zum jeweiligen Algorithmus \cite{bib:antsystem}\cite{bib:antcolonysystem}\cite{bib:antq}\cite{bib:antqprops} gefunden werden.

\subsection{Verwendete Parameter}

Folgende Parameter wurden für nachfolgend abgebildeten Verläufe verwendet:

\begin{enumerate}
	\item \textbf{Ant System:}
	\begin{itemize}
		\item $m = 10$
		\item $\alpha = 1$
		\item $\beta = 5$
		\item $\rho = 0.1$
		\item $Q = 100$
		\item $\tau_0 = 10$
	\end{itemize}
	\item \textbf{Ant Colony System:}
	\begin{itemize}
		\item $m = 10$
		\item $\alpha = 1$
		\item $\beta = 5$
		\item $\rho_{global} = 0.1$
		\item $\rho_{lokal} = 0.1$
		\item $q_0 = 0.5$
		\item $\tau_0 = (30 \cdot 530) ^{-1}$
	\end{itemize}
	\item \textbf{Ant-Q:}
	\begin{itemize}
		\item $m = 10$
		\item $\alpha = 1$
		\item $\beta = 5$
		\item $\rho_{global} = 0.1$
		\item $\rho_{lokal} = 0.1$
		\item $\gamma = 0.01$
		\item $q_0 = 0.5$
		\item $\tau_0 = (30 \cdot 530) ^{-1}$
	\end{itemize}
\end{enumerate}

Die Werte von $\tau_0$ wurden gemäss der von den Autoren von \textbf{ACS} und \textbf{Ant-Q} Vorgeschlagenen Formel $\tau_0 = (n \cdot L_{nn}) ^{-1}$ berechnet; $L_{nn}$ ist die Länge einer durch
die \textbf{Nearest Neighbor}-Technik erstellten Route.

\begin{figure}[p]
	\centering
	\caption{Ant System}
	\includegraphics[width=\textwidth]{ant_system.pdf}
	\caption{Ant Colony System}
	\includegraphics[width=\textwidth]{ant_colony_system.pdf}
\end{figure}

\begin{figure}[p]
	\caption{Ant-Q}
	\centering
	\includegraphics[width=\textwidth]{ant_q.pdf}
\end{figure}

\begin{sidewaysfigure}[p]
	\caption{Graphendarstellung des Oliver30-TSP. Der rot eingezeichnete Pfad entspricht der optimalen Lösung.}
	\centering
	\begin{tikzpicture}[scale=0.125,x=0.09\linewidth](0,0)(80,80)
		\node[fill=white,draw,circle] at (54,67)	(01) {01};
		\node[fill=white,draw,circle] at (54,62)	(02) {02};
		\node[fill=white,draw,circle] at (37,84)	(03) {03};
		\node[fill=white,draw,circle] at (41,94)	(04) {04};
		\node[fill=white,draw,circle] at (2,99)		(05) {05};
		\node[fill=white,draw,circle] at (7,64)		(06) {06};
		\node[fill=white,draw,circle] at (25,62)	(07) {07};
		\node[fill=white,draw,circle] at (22,60)	(08) {08};
		\node[fill=white,draw,circle] at (18,54)	(09) {09};
		\node[fill=white,draw,circle] at (4,50)		(10) {10};
		\node[fill=white,draw,circle] at (13,40)	(11) {11};
		\node[fill=white,draw,circle] at (18,40)	(12) {12};
		\node[fill=white,draw,circle] at (24,42)	(13) {13};
		\node[fill=white,draw,circle] at (25,38)	(14) {14};
		\node[fill=white,draw,circle] at (44,35)	(15) {15};
		\node[fill=white,draw,circle] at (41,26)	(16) {16};
		\node[fill=white,draw,circle] at (45,21)	(17) {17};
		\node[fill=white,draw,circle] at (58,35)	(18) {18};
		\node[fill=white,draw,circle] at (62,32)	(19) {19};
		\node[fill=white,draw,circle] at (82,7)		(20) {20};
		\node[fill=white,draw,circle] at (91,38)	(21) {21};
		\node[fill=white,draw,circle] at (83,46)	(22) {22};
		\node[fill=white,draw,circle] at (71,44)	(23) {23};
		\node[fill=white,draw,circle] at (64,60)	(24) {24};
		\node[fill=white,draw,circle] at (68,58)	(25) {25};
		\node[fill=white,draw,circle] at (83,69)	(26) {26};
		\node[fill=white,draw,circle] at (87,76)	(27) {27};
		\node[fill=white,draw,circle] at (74,78)	(28) {28};
		\node[fill=white,draw,circle] at (71,71)	(29) {29};
		\node[fill=white,draw,circle] at (58,69)	(30) {30};
		
		\begin{pgfonlayer}{bg}
			\draw[gray!60,-] (01) edge (01);
			\draw[gray!60,-] (01) edge (02);
			\draw[gray!60,-] (01) edge (03);
			\draw[gray!60,-] (01) edge (04);
			\draw[gray!60,-] (01) edge (05);
			\draw[gray!60,-] (01) edge (06);
			\draw[gray!60,-] (01) edge (07);
			\draw[gray!60,-] (01) edge (08);
			\draw[gray!60,-] (01) edge (09);
			\draw[gray!60,-] (01) edge (10);
			\draw[gray!60,-] (01) edge (11);
			\draw[gray!60,-] (01) edge (12);
			\draw[gray!60,-] (01) edge (13);
			\draw[gray!60,-] (01) edge (14);
			\draw[gray!60,-] (01) edge (15);
			\draw[gray!60,-] (01) edge (16);
			\draw[gray!60,-] (01) edge (17);
			\draw[gray!60,-] (01) edge (18);
			\draw[gray!60,-] (01) edge (19);
			\draw[gray!60,-] (01) edge (20);
			\draw[gray!60,-] (01) edge (21);
			\draw[gray!60,-] (01) edge (22);
			\draw[gray!60,-] (01) edge (23);
			\draw[gray!60,-] (01) edge (24);
			\draw[gray!60,-] (01) edge (25);
			\draw[gray!60,-] (01) edge (26);
			\draw[gray!60,-] (01) edge (27);
			\draw[gray!60,-] (01) edge (28);
			\draw[gray!60,-] (01) edge (29);
			\draw[gray!60,-] (01) edge (30);
			\draw[gray!60,-] (02) edge (02);
			\draw[gray!60,-] (02) edge (03);
			\draw[gray!60,-] (02) edge (04);
			\draw[gray!60,-] (02) edge (05);
			\draw[gray!60,-] (02) edge (06);
			\draw[gray!60,-] (02) edge (07);
			\draw[gray!60,-] (02) edge (08);
			\draw[gray!60,-] (02) edge (09);
			\draw[gray!60,-] (02) edge (10);
			\draw[gray!60,-] (02) edge (11);
			\draw[gray!60,-] (02) edge (12);
			\draw[gray!60,-] (02) edge (13);
			\draw[gray!60,-] (02) edge (14);
			\draw[gray!60,-] (02) edge (15);
			\draw[gray!60,-] (02) edge (16);
			\draw[gray!60,-] (02) edge (17);
			\draw[gray!60,-] (02) edge (18);
			\draw[gray!60,-] (02) edge (19);
			\draw[gray!60,-] (02) edge (20);
			\draw[gray!60,-] (02) edge (21);
			\draw[gray!60,-] (02) edge (22);
			\draw[gray!60,-] (02) edge (23);
			\draw[gray!60,-] (02) edge (24);
			\draw[gray!60,-] (02) edge (25);
			\draw[gray!60,-] (02) edge (26);
			\draw[gray!60,-] (02) edge (27);
			\draw[gray!60,-] (02) edge (28);
			\draw[gray!60,-] (02) edge (29);
			\draw[gray!60,-] (02) edge (30);
			\draw[gray!60,-] (03) edge (03);
			\draw[gray!60,-] (03) edge (04);
			\draw[gray!60,-] (03) edge (05);
			\draw[gray!60,-] (03) edge (06);
			\draw[gray!60,-] (03) edge (07);
			\draw[gray!60,-] (03) edge (08);
			\draw[gray!60,-] (03) edge (09);
			\draw[gray!60,-] (03) edge (10);
			\draw[gray!60,-] (03) edge (11);
			\draw[gray!60,-] (03) edge (12);
			\draw[gray!60,-] (03) edge (13);
			\draw[gray!60,-] (03) edge (14);
			\draw[gray!60,-] (03) edge (15);
			\draw[gray!60,-] (03) edge (16);
			\draw[gray!60,-] (03) edge (17);
			\draw[gray!60,-] (03) edge (18);
			\draw[gray!60,-] (03) edge (19);
			\draw[gray!60,-] (03) edge (20);
			\draw[gray!60,-] (03) edge (21);
			\draw[gray!60,-] (03) edge (22);
			\draw[gray!60,-] (03) edge (23);
			\draw[gray!60,-] (03) edge (24);
			\draw[gray!60,-] (03) edge (25);
			\draw[gray!60,-] (03) edge (26);
			\draw[gray!60,-] (03) edge (27);
			\draw[gray!60,-] (03) edge (28);
			\draw[gray!60,-] (03) edge (29);
			\draw[gray!60,-] (03) edge (30);
			\draw[gray!60,-] (04) edge (04);
			\draw[gray!60,-] (04) edge (05);
			\draw[gray!60,-] (04) edge (06);
			\draw[gray!60,-] (04) edge (07);
			\draw[gray!60,-] (04) edge (08);
			\draw[gray!60,-] (04) edge (09);
			\draw[gray!60,-] (04) edge (10);
			\draw[gray!60,-] (04) edge (11);
			\draw[gray!60,-] (04) edge (12);
			\draw[gray!60,-] (04) edge (13);
			\draw[gray!60,-] (04) edge (14);
			\draw[gray!60,-] (04) edge (15);
			\draw[gray!60,-] (04) edge (16);
			\draw[gray!60,-] (04) edge (17);
			\draw[gray!60,-] (04) edge (18);
			\draw[gray!60,-] (04) edge (19);
			\draw[gray!60,-] (04) edge (20);
			\draw[gray!60,-] (04) edge (21);
			\draw[gray!60,-] (04) edge (22);
			\draw[gray!60,-] (04) edge (23);
			\draw[gray!60,-] (04) edge (24);
			\draw[gray!60,-] (04) edge (25);
			\draw[gray!60,-] (04) edge (26);
			\draw[gray!60,-] (04) edge (27);
			\draw[gray!60,-] (04) edge (28);
			\draw[gray!60,-] (04) edge (29);
			\draw[gray!60,-] (04) edge (30);
			\draw[gray!60,-] (05) edge (05);
			\draw[gray!60,-] (05) edge (06);
			\draw[gray!60,-] (05) edge (07);
			\draw[gray!60,-] (05) edge (08);
			\draw[gray!60,-] (05) edge (09);
			\draw[gray!60,-] (05) edge (10);
			\draw[gray!60,-] (05) edge (11);
			\draw[gray!60,-] (05) edge (12);
			\draw[gray!60,-] (05) edge (13);
			\draw[gray!60,-] (05) edge (14);
			\draw[gray!60,-] (05) edge (15);
			\draw[gray!60,-] (05) edge (16);
			\draw[gray!60,-] (05) edge (17);
			\draw[gray!60,-] (05) edge (18);
			\draw[gray!60,-] (05) edge (19);
			\draw[gray!60,-] (05) edge (20);
			\draw[gray!60,-] (05) edge (21);
			\draw[gray!60,-] (05) edge (22);
			\draw[gray!60,-] (05) edge (23);
			\draw[gray!60,-] (05) edge (24);
			\draw[gray!60,-] (05) edge (25);
			\draw[gray!60,-] (05) edge (26);
			\draw[gray!60,-] (05) edge (27);
			\draw[gray!60,-] (05) edge (28);
			\draw[gray!60,-] (05) edge (29);
			\draw[gray!60,-] (05) edge (30);
			\draw[gray!60,-] (06) edge (06);
			\draw[gray!60,-] (06) edge (07);
			\draw[gray!60,-] (06) edge (08);
			\draw[gray!60,-] (06) edge (09);
			\draw[gray!60,-] (06) edge (10);
			\draw[gray!60,-] (06) edge (11);
			\draw[gray!60,-] (06) edge (12);
			\draw[gray!60,-] (06) edge (13);
			\draw[gray!60,-] (06) edge (14);
			\draw[gray!60,-] (06) edge (15);
			\draw[gray!60,-] (06) edge (16);
			\draw[gray!60,-] (06) edge (17);
			\draw[gray!60,-] (06) edge (18);
			\draw[gray!60,-] (06) edge (19);
			\draw[gray!60,-] (06) edge (20);
			\draw[gray!60,-] (06) edge (21);
			\draw[gray!60,-] (06) edge (22);
			\draw[gray!60,-] (06) edge (23);
			\draw[gray!60,-] (06) edge (24);
			\draw[gray!60,-] (06) edge (25);
			\draw[gray!60,-] (06) edge (26);
			\draw[gray!60,-] (06) edge (27);
			\draw[gray!60,-] (06) edge (28);
			\draw[gray!60,-] (06) edge (29);
			\draw[gray!60,-] (06) edge (30);
			\draw[gray!60,-] (07) edge (07);
			\draw[gray!60,-] (07) edge (08);
			\draw[gray!60,-] (07) edge (09);
			\draw[gray!60,-] (07) edge (10);
			\draw[gray!60,-] (07) edge (11);
			\draw[gray!60,-] (07) edge (12);
			\draw[gray!60,-] (07) edge (13);
			\draw[gray!60,-] (07) edge (14);
			\draw[gray!60,-] (07) edge (15);
			\draw[gray!60,-] (07) edge (16);
			\draw[gray!60,-] (07) edge (17);
			\draw[gray!60,-] (07) edge (18);
			\draw[gray!60,-] (07) edge (19);
			\draw[gray!60,-] (07) edge (20);
			\draw[gray!60,-] (07) edge (21);
			\draw[gray!60,-] (07) edge (22);
			\draw[gray!60,-] (07) edge (23);
			\draw[gray!60,-] (07) edge (24);
			\draw[gray!60,-] (07) edge (25);
			\draw[gray!60,-] (07) edge (26);
			\draw[gray!60,-] (07) edge (27);
			\draw[gray!60,-] (07) edge (28);
			\draw[gray!60,-] (07) edge (29);
			\draw[gray!60,-] (07) edge (30);
			\draw[gray!60,-] (08) edge (08);
			\draw[gray!60,-] (08) edge (09);
			\draw[gray!60,-] (08) edge (10);
			\draw[gray!60,-] (08) edge (11);
			\draw[gray!60,-] (08) edge (12);
			\draw[gray!60,-] (08) edge (13);
			\draw[gray!60,-] (08) edge (14);
			\draw[gray!60,-] (08) edge (15);
			\draw[gray!60,-] (08) edge (16);
			\draw[gray!60,-] (08) edge (17);
			\draw[gray!60,-] (08) edge (18);
			\draw[gray!60,-] (08) edge (19);
			\draw[gray!60,-] (08) edge (20);
			\draw[gray!60,-] (08) edge (21);
			\draw[gray!60,-] (08) edge (22);
			\draw[gray!60,-] (08) edge (23);
			\draw[gray!60,-] (08) edge (24);
			\draw[gray!60,-] (08) edge (25);
			\draw[gray!60,-] (08) edge (26);
			\draw[gray!60,-] (08) edge (27);
			\draw[gray!60,-] (08) edge (28);
			\draw[gray!60,-] (08) edge (29);
			\draw[gray!60,-] (08) edge (30);
			\draw[gray!60,-] (09) edge (09);
			\draw[gray!60,-] (09) edge (10);
			\draw[gray!60,-] (09) edge (11);
			\draw[gray!60,-] (09) edge (12);
			\draw[gray!60,-] (09) edge (13);
			\draw[gray!60,-] (09) edge (14);
			\draw[gray!60,-] (09) edge (15);
			\draw[gray!60,-] (09) edge (16);
			\draw[gray!60,-] (09) edge (17);
			\draw[gray!60,-] (09) edge (18);
			\draw[gray!60,-] (09) edge (19);
			\draw[gray!60,-] (09) edge (20);
			\draw[gray!60,-] (09) edge (21);
			\draw[gray!60,-] (09) edge (22);
			\draw[gray!60,-] (09) edge (23);
			\draw[gray!60,-] (09) edge (24);
			\draw[gray!60,-] (09) edge (25);
			\draw[gray!60,-] (09) edge (26);
			\draw[gray!60,-] (09) edge (27);
			\draw[gray!60,-] (09) edge (28);
			\draw[gray!60,-] (09) edge (29);
			\draw[gray!60,-] (09) edge (30);
			\draw[gray!60,-] (10) edge (10);
			\draw[gray!60,-] (10) edge (11);
			\draw[gray!60,-] (10) edge (12);
			\draw[gray!60,-] (10) edge (13);
			\draw[gray!60,-] (10) edge (14);
			\draw[gray!60,-] (10) edge (15);
			\draw[gray!60,-] (10) edge (16);
			\draw[gray!60,-] (10) edge (17);
			\draw[gray!60,-] (10) edge (18);
			\draw[gray!60,-] (10) edge (19);
			\draw[gray!60,-] (10) edge (20);
			\draw[gray!60,-] (10) edge (21);
			\draw[gray!60,-] (10) edge (22);
			\draw[gray!60,-] (10) edge (23);
			\draw[gray!60,-] (10) edge (24);
			\draw[gray!60,-] (10) edge (25);
			\draw[gray!60,-] (10) edge (26);
			\draw[gray!60,-] (10) edge (27);
			\draw[gray!60,-] (10) edge (28);
			\draw[gray!60,-] (10) edge (29);
			\draw[gray!60,-] (10) edge (30);
			\draw[gray!60,-] (11) edge (11);
			\draw[gray!60,-] (11) edge (12);
			\draw[gray!60,-] (11) edge (13);
			\draw[gray!60,-] (11) edge (14);
			\draw[gray!60,-] (11) edge (15);
			\draw[gray!60,-] (11) edge (16);
			\draw[gray!60,-] (11) edge (17);
			\draw[gray!60,-] (11) edge (18);
			\draw[gray!60,-] (11) edge (19);
			\draw[gray!60,-] (11) edge (20);
			\draw[gray!60,-] (11) edge (21);
			\draw[gray!60,-] (11) edge (22);
			\draw[gray!60,-] (11) edge (23);
			\draw[gray!60,-] (11) edge (24);
			\draw[gray!60,-] (11) edge (25);
			\draw[gray!60,-] (11) edge (26);
			\draw[gray!60,-] (11) edge (27);
			\draw[gray!60,-] (11) edge (28);
			\draw[gray!60,-] (11) edge (29);
			\draw[gray!60,-] (11) edge (30);
			\draw[gray!60,-] (12) edge (12);
			\draw[gray!60,-] (12) edge (13);
			\draw[gray!60,-] (12) edge (14);
			\draw[gray!60,-] (12) edge (15);
			\draw[gray!60,-] (12) edge (16);
			\draw[gray!60,-] (12) edge (17);
			\draw[gray!60,-] (12) edge (18);
			\draw[gray!60,-] (12) edge (19);
			\draw[gray!60,-] (12) edge (20);
			\draw[gray!60,-] (12) edge (21);
			\draw[gray!60,-] (12) edge (22);
			\draw[gray!60,-] (12) edge (23);
			\draw[gray!60,-] (12) edge (24);
			\draw[gray!60,-] (12) edge (25);
			\draw[gray!60,-] (12) edge (26);
			\draw[gray!60,-] (12) edge (27);
			\draw[gray!60,-] (12) edge (28);
			\draw[gray!60,-] (12) edge (29);
			\draw[gray!60,-] (12) edge (30);
			\draw[gray!60,-] (13) edge (13);
			\draw[gray!60,-] (13) edge (14);
			\draw[gray!60,-] (13) edge (15);
			\draw[gray!60,-] (13) edge (16);
			\draw[gray!60,-] (13) edge (17);
			\draw[gray!60,-] (13) edge (18);
			\draw[gray!60,-] (13) edge (19);
			\draw[gray!60,-] (13) edge (20);
			\draw[gray!60,-] (13) edge (21);
			\draw[gray!60,-] (13) edge (22);
			\draw[gray!60,-] (13) edge (23);
			\draw[gray!60,-] (13) edge (24);
			\draw[gray!60,-] (13) edge (25);
			\draw[gray!60,-] (13) edge (26);
			\draw[gray!60,-] (13) edge (27);
			\draw[gray!60,-] (13) edge (28);
			\draw[gray!60,-] (13) edge (29);
			\draw[gray!60,-] (13) edge (30);
			\draw[gray!60,-] (14) edge (14);
			\draw[gray!60,-] (14) edge (15);
			\draw[gray!60,-] (14) edge (16);
			\draw[gray!60,-] (14) edge (17);
			\draw[gray!60,-] (14) edge (18);
			\draw[gray!60,-] (14) edge (19);
			\draw[gray!60,-] (14) edge (20);
			\draw[gray!60,-] (14) edge (21);
			\draw[gray!60,-] (14) edge (22);
			\draw[gray!60,-] (14) edge (23);
			\draw[gray!60,-] (14) edge (24);
			\draw[gray!60,-] (14) edge (25);
			\draw[gray!60,-] (14) edge (26);
			\draw[gray!60,-] (14) edge (27);
			\draw[gray!60,-] (14) edge (28);
			\draw[gray!60,-] (14) edge (29);
			\draw[gray!60,-] (14) edge (30);
			\draw[gray!60,-] (15) edge (15);
			\draw[gray!60,-] (15) edge (16);
			\draw[gray!60,-] (15) edge (17);
			\draw[gray!60,-] (15) edge (18);
			\draw[gray!60,-] (15) edge (19);
			\draw[gray!60,-] (15) edge (20);
			\draw[gray!60,-] (15) edge (21);
			\draw[gray!60,-] (15) edge (22);
			\draw[gray!60,-] (15) edge (23);
			\draw[gray!60,-] (15) edge (24);
			\draw[gray!60,-] (15) edge (25);
			\draw[gray!60,-] (15) edge (26);
			\draw[gray!60,-] (15) edge (27);
			\draw[gray!60,-] (15) edge (28);
			\draw[gray!60,-] (15) edge (29);
			\draw[gray!60,-] (15) edge (30);
			\draw[gray!60,-] (16) edge (16);
			\draw[gray!60,-] (16) edge (17);
			\draw[gray!60,-] (16) edge (18);
			\draw[gray!60,-] (16) edge (19);
			\draw[gray!60,-] (16) edge (20);
			\draw[gray!60,-] (16) edge (21);
			\draw[gray!60,-] (16) edge (22);
			\draw[gray!60,-] (16) edge (23);
			\draw[gray!60,-] (16) edge (24);
			\draw[gray!60,-] (16) edge (25);
			\draw[gray!60,-] (16) edge (26);
			\draw[gray!60,-] (16) edge (27);
			\draw[gray!60,-] (16) edge (28);
			\draw[gray!60,-] (16) edge (29);
			\draw[gray!60,-] (16) edge (30);
			\draw[gray!60,-] (17) edge (17);
			\draw[gray!60,-] (17) edge (18);
			\draw[gray!60,-] (17) edge (19);
			\draw[gray!60,-] (17) edge (20);
			\draw[gray!60,-] (17) edge (21);
			\draw[gray!60,-] (17) edge (22);
			\draw[gray!60,-] (17) edge (23);
			\draw[gray!60,-] (17) edge (24);
			\draw[gray!60,-] (17) edge (25);
			\draw[gray!60,-] (17) edge (26);
			\draw[gray!60,-] (17) edge (27);
			\draw[gray!60,-] (17) edge (28);
			\draw[gray!60,-] (17) edge (29);
			\draw[gray!60,-] (17) edge (30);
			\draw[gray!60,-] (18) edge (18);
			\draw[gray!60,-] (18) edge (19);
			\draw[gray!60,-] (18) edge (20);
			\draw[gray!60,-] (18) edge (21);
			\draw[gray!60,-] (18) edge (22);
			\draw[gray!60,-] (18) edge (23);
			\draw[gray!60,-] (18) edge (24);
			\draw[gray!60,-] (18) edge (25);
			\draw[gray!60,-] (18) edge (26);
			\draw[gray!60,-] (18) edge (27);
			\draw[gray!60,-] (18) edge (28);
			\draw[gray!60,-] (18) edge (29);
			\draw[gray!60,-] (18) edge (30);
			\draw[gray!60,-] (19) edge (19);
			\draw[gray!60,-] (19) edge (20);
			\draw[gray!60,-] (19) edge (21);
			\draw[gray!60,-] (19) edge (22);
			\draw[gray!60,-] (19) edge (23);
			\draw[gray!60,-] (19) edge (24);
			\draw[gray!60,-] (19) edge (25);
			\draw[gray!60,-] (19) edge (26);
			\draw[gray!60,-] (19) edge (27);
			\draw[gray!60,-] (19) edge (28);
			\draw[gray!60,-] (19) edge (29);
			\draw[gray!60,-] (19) edge (30);
			\draw[gray!60,-] (20) edge (20);
			\draw[gray!60,-] (20) edge (21);
			\draw[gray!60,-] (20) edge (22);
			\draw[gray!60,-] (20) edge (23);
			\draw[gray!60,-] (20) edge (24);
			\draw[gray!60,-] (20) edge (25);
			\draw[gray!60,-] (20) edge (26);
			\draw[gray!60,-] (20) edge (27);
			\draw[gray!60,-] (20) edge (28);
			\draw[gray!60,-] (20) edge (29);
			\draw[gray!60,-] (20) edge (30);
			\draw[gray!60,-] (21) edge (21);
			\draw[gray!60,-] (21) edge (22);
			\draw[gray!60,-] (21) edge (23);
			\draw[gray!60,-] (21) edge (24);
			\draw[gray!60,-] (21) edge (25);
			\draw[gray!60,-] (21) edge (26);
			\draw[gray!60,-] (21) edge (27);
			\draw[gray!60,-] (21) edge (28);
			\draw[gray!60,-] (21) edge (29);
			\draw[gray!60,-] (21) edge (30);
			\draw[gray!60,-] (22) edge (22);
			\draw[gray!60,-] (22) edge (23);
			\draw[gray!60,-] (22) edge (24);
			\draw[gray!60,-] (22) edge (25);
			\draw[gray!60,-] (22) edge (26);
			\draw[gray!60,-] (22) edge (27);
			\draw[gray!60,-] (22) edge (28);
			\draw[gray!60,-] (22) edge (29);
			\draw[gray!60,-] (22) edge (30);
			\draw[gray!60,-] (23) edge (23);
			\draw[gray!60,-] (23) edge (24);
			\draw[gray!60,-] (23) edge (25);
			\draw[gray!60,-] (23) edge (26);
			\draw[gray!60,-] (23) edge (27);
			\draw[gray!60,-] (23) edge (28);
			\draw[gray!60,-] (23) edge (29);
			\draw[gray!60,-] (23) edge (30);
			\draw[gray!60,-] (24) edge (24);
			\draw[gray!60,-] (24) edge (25);
			\draw[gray!60,-] (24) edge (26);
			\draw[gray!60,-] (24) edge (27);
			\draw[gray!60,-] (24) edge (28);
			\draw[gray!60,-] (24) edge (29);
			\draw[gray!60,-] (24) edge (30);
			\draw[gray!60,-] (25) edge (25);
			\draw[gray!60,-] (25) edge (26);
			\draw[gray!60,-] (25) edge (27);
			\draw[gray!60,-] (25) edge (28);
			\draw[gray!60,-] (25) edge (29);
			\draw[gray!60,-] (25) edge (30);
			\draw[gray!60,-] (26) edge (26);
			\draw[gray!60,-] (26) edge (27);
			\draw[gray!60,-] (26) edge (28);
			\draw[gray!60,-] (26) edge (29);
			\draw[gray!60,-] (26) edge (30);
			\draw[gray!60,-] (27) edge (27);
			\draw[gray!60,-] (27) edge (28);
			\draw[gray!60,-] (27) edge (29);
			\draw[gray!60,-] (27) edge (30);
			\draw[gray!60,-] (28) edge (28);
			\draw[gray!60,-] (28) edge (29);
			\draw[gray!60,-] (28) edge (30);
			\draw[gray!60,-] (29) edge (29);
			\draw[gray!60,-] (29) edge (30);
			\draw[gray!60,-] (30) edge (30);
			
			\draw[red,-] (01) edge (03);
			\draw[red,-] (03) edge (04);
			\draw[red,-] (04) edge (05);
			\draw[red,-] (05) edge (06);
			\draw[red,-] (06) edge (07);
			\draw[red,-] (07) edge (08);
			\draw[red,-] (08) edge (09);
			\draw[red,-] (09) edge (10);
			\draw[red,-] (10) edge (11);
			\draw[red,-] (11) edge (12);
			\draw[red,-] (12) edge (13);
			\draw[red,-] (13) edge (14);
			\draw[red,-] (14) edge (15);
			\draw[red,-] (15) edge (16);
			\draw[red,-] (16) edge (17);
			\draw[red,-] (17) edge (18);
			\draw[red,-] (18) edge (19);
			\draw[red,-] (19) edge (20);
			\draw[red,-] (20) edge (21);
			\draw[red,-] (21) edge (22);
			\draw[red,-] (22) edge (23);
			\draw[red,-] (23) edge (25);
			\draw[red,-] (25) edge (24);
			\draw[red,-] (24) edge (26);
			\draw[red,-] (26) edge (27);
			\draw[red,-] (27) edge (28);
			\draw[red,-] (28) edge (29);
			\draw[red,-] (29) edge (30);
			\draw[red,-] (30) edge (02);
			\draw[red,-] (02) edge (01);
		\end{pgfonlayer}
	\end{tikzpicture}
\end{sidewaysfigure}

\clearpage
%
% ---- Bibliography ----
%
\begin{thebibliography}{5}
%
\bibitem {bib:antsystem}
Marco Dorigo, Vittorio Maniezzo, Alberto Colorni:
The Ant System:
Optimization by a colony of cooperating agent,
\href{ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf}{ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf},
Stand: Januar 2012

\bibitem {bib:antcolonysystem}
Marco Dorigo, Luca Maria Gambardella:
Ant Colony System:
A Cooperative Learning Approach to the Traveling Salesman Problem,
\href{http://www.idsia.ch/~luca/acs-ec97.pdf}{http://www.idsia.ch/~luca/acs-ec97.pdf},
Stand: Januar 2012

\bibitem {bib:antq}
Marco Dorigo, Luca Maria Gambardella:
Ant-Q: 
A Reinforcement Learning Approach to the Traveling Salesman Problem,
\href{http://www.idsia.ch/~luca/ml95.pdf}{http://www.idsia.ch/~luca/ml95.pdf},
Stand: Januar 2012

\bibitem {bib:antqprops}
Marco Dorigo, Luca Maria Gambardella:
A Study of some Properties of Ant-Q,
\href{http://www.idsia.ch/~luca/abstracts/papers/ppsn96.pdf}{http://www.idsia.ch/~luca/abstracts/papers/ppsn96.pdf},
Stand Januar 2012

\bibitem {bib:oliver}
I.M. Oliver, D.J. Smith,  and J.R.C. Holland,  
A Study of Permutation Crossover Operators on the Traveling Salesman Problem,  
in Proc. ICGA, 1987, pp.224-230. 

\bibitem {bib:wikipedia_ants}
Wikipedia: Ameisenalgorithmus,
\href{http://de.wikipedia.org/wiki/Ameisenalgorithmus}{http://de.wikipedia.org/wiki/Ameisenalgorithmus} (deutsch),
\href{http://en.wikipedia.org/wiki/Ant\_colony\_optimization\_algorithms}{http://en.wikipedia.org/wiki/Ant\_colony\_optimization\_algorithms} (englisch),
Stand: Januar 2012

\bibitem {bib:wikipedia_stigmergy}
Wikipedia: Stigmergie,
\href{http://de.wikipedia.org/wiki/Stigmergie}{http://de.wikipedia.org/wiki/Stigmergie} (deutsch),
\href{http://en.wikipedia.org/wiki/Stigmergy}{http://en.wikipedia.org/wiki/Stigmergy} (englisch),
Stand: Januar 2012

\end{thebibliography}

\clearpage

\begin{appendix}  
\section*{Appendix}
\section{Beilagen}
Angehängt an diese Arbeit befinden sich die Quelltexte der vorgestellten Algorithmen in GNU Octave:
\begin{enumerate}
	\item{AntSystem.m}
	\item{AntColonySystem.m}
	\item{AntQ.m}
\end{enumerate}

\clearpage
\section{Ant System}\label{appendix:AS}

\begin{algorithm}[hhh!]
  \caption{Ant System Umsetzung des TSP}
	\begin{algorithmic}
	\Function{AntSystem}{$Towns, \delta, n_{Ants}, i_{max}, \tau_{0}, Q, \alpha, \beta$}
		\State $i \gets 0$ \Comment Initialisierung
		\State $ShortestTour \gets \text{empty Set of Edges}$
		\State $L_{min} \gets \infty$
		\State $\tau \gets \text{Array of Floating Point Numbers}$
		\State $\Delta\tau \gets \text{Array of Floating Point Numbers}$
		\For{$\forall (i,j), i \in Towns, j \in Towns$}
			\State $\tau[i,j] \gets \tau_{0}$
			\State $\Delta\tau[i,j] \gets 0$
		\EndFor
		\While{$i < i_{max}$} \Comment Die Hauptschleife
			\State $i \gets i+1$
			\State $StartingTown \gets \text{Array}[n_{Ants}]\text{ of Towns}$
			\State \textbf{shuffle} $Towns$ \Comment Verteile die Ameisen zufällig auf verschiedene Städte
			\For{$Ant \gets 1\dots{}n_{Ants}$}
				\State $StartingTown[Ant] \gets Towns[Ant \mod length(Towns)]$
			\EndFor
			\For{$Ant \gets 1\dots{}n_{Ants}$} \Comment Berechne eine Tour für jede Ameise
				\State $VisitedTowns \gets \text{empty Set of Towns}$
				\State $VisitedEdges \gets \text{empty Set of Edges}$
				\State $ActualTown \gets StartingTown[Ant]$
				\State add $StartingTown[Ant]$ to $VisitedTowns$
				\State $L \gets 0$
				\While{$\exists Town, Town \in Towns \setminus VisitedTowns$}
					\State $a_{total} \gets 0$ \Comment Berechne die Attraktivität aller möglichen KAnten
					\State $a \gets \text{Array of Floating Point Number}$  
					\For{$\forall NextTown, NextTown \in Towns \setminus VisitedTowns$}
						\State $a[NextTown] \gets [\tau(ActualTown,NextTown)] ^ \alpha \cdot [\delta(ActualTown,NextTown)] ^ \beta$
						\State $a_{total} \gets a_{total} + a[NextTown]$
					\EndFor
				\algstore{alg:AS}
	\end{algorithmic}
\end{algorithm}
\vfill

\begin{algorithm}[hhh!]
  \ContinuedFloat
  \caption{Ant System Umsetzung des TSP (2.Teil)}
	\begin{algorithmic}
				\algrestore{alg:AS}
					\State $rnd \gets Random(0,1)$ \Comment Wähle die nächste Stadt
					\For{$\forall NextTown, NextTown \in Towns \setminus VisitedTowns$}
						\State $p \gets a[NextTown] / a_{total}$
						\If{$rnd \leq p$}
							\State add $(ActualTown,NextTown)$ to $VisitedEdges$
							\State add $NextTown$ to $VisitedTowns$
							\State $L \gets L + \delta[ActualTown,NextTown]$
							\State $ActualTown \gets NextTown$
							\State \textbf{break}
						\EndIf
						\State $rnd \gets rnd - p$
					\EndFor
				\EndWhile
				\State add $(ActualTown,StartingTown[Ant])$ to $VisitedEdges$
				\State $L \gets L + \delta[ActualTown,StartingTown[Ant]]$
				\For{$\forall (i,j) \in VisitedEdges$}
					\State $\Delta\tau[i,j] \gets \Delta\tau[i,j] + \frac{Q}{L}$
					\State $\Delta\tau[j,i] \gets \Delta\tau[i,j]$ \Comment Nur für symmetrische TSP!
				\EndFor
				\If{$L < L_{min}$}
					\State $L_{min} \gets L$
					\State $ShortestTour \gets VisitedEdges$
				\EndIf
			\EndFor
			\For{$\forall (i,j), i \in Towns, j \in Towns$} \Comment Berechne die neuen Pheromonwerte
				\State $\tau[i,j] \gets \rho \cdot \tau[i,j] + \Delta\tau[i,j]$
				\State $\Delta\tau[i,j] \gets 0$
			\EndFor
		\EndWhile
		\State \textbf{return} $ShortestTour$
	\EndFunction
	\end{algorithmic}
	\vfill
\end{algorithm}
\vfill

\clearpage
\section{Ant Colony System}\label{appendix:ACS}

\begin{algorithm}[hhh!]
  \caption{Ant Colony System Umsetzung des TSP}
	\begin{algorithmic}
	\Function{AntSystem}{$Towns, \delta, n_{Ants}, i_{max}, \tau_{0}, q_0, \alpha, \beta, \rho_{global}, \rho_{lokal}$}
		\State $i \gets 0$ \Comment Initialisierung
		\State $ShortestTour \gets \text{empty Set of Edges}$
		\State $L_{min} \gets \infty$
		\State $\tau \gets \text{Array of Floating Point Numbers}$
		\For{$\forall (i,j), i \in Towns, j \in Towns$}
			\State $\tau[i,j] \gets \tau_{0}$
		\EndFor
		\While{$i < i_{max}$} \Comment Die Hauptschleife
			\State $i \gets i+1$
			\State $StartingTown \gets \text{Array}[n_{Ants}]\text{ of Towns}$
			\State \textbf{shuffle} $Towns$ \Comment Verteile die Ameisen zufällig auf verschiedene Städte
			\For{$Ant \gets 1\dots{}n_{Ants}$}
				\State $StartingTown[Ant] \gets Towns[Ant \mod length(Towns)]$
			\EndFor
			\For{$Ant \gets 1\dots{}n_{Ants}$} \Comment Berechne eine Tour für jede Ameise
				\State $VisitedTowns \gets \text{empty Set of Towns}$
				\State $VisitedEdges \gets \text{empty Set of Edges}$
				\State $ActualTown \gets StartingTown[Ant]$
				\State add $StartingTown[Ant]$ to $VisitedTowns$
				\State $L \gets 0$
				\While{$\exists Town, Town \in Towns \setminus VisitedTowns$}
					\State $rnd \gets Random(0,1)$ \Comment Wähle die nächste Stadt
					\State $a_{total} \gets 0$ \Comment Berechne die Attraktivität aller möglichen Kanten
					\State $a \gets \text{Array of Floating Point Number}$  
					\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
						\State $a[Town] \gets [\tau(ActualTown,Town)] ^ \alpha \cdot [\delta(ActualTown,Town)] ^ \beta$
						\State $a_{total} \gets a_{total} + a[Town]$
					\EndFor
					\State $NextTown \gets NULL$
					\If{$rnd \leq q_0$} \Comment Fall 1: Wähle die beste Kante
						\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
							\If{$a(ActualTown,Town) < \delta(ActualTown,NextTown)$}
								\State $NextTown \gets Town$ 
							\EndIf
						\EndFor
				\algstore{alg:ACS}
	\end{algorithmic}
\end{algorithm}
\vfill

\begin{algorithm}[hhh!]
  \ContinuedFloat
  \caption{Ant Colony System Umsetzung des TSP (2.Teil)}
	\begin{algorithmic}
				\algrestore{alg:ACS}
					\Else \Comment Fall 2: Wähle zufällig zwischen den Kanten
						\State $rnd \gets (rnd - q_0) / (1 - q_0)$
						\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
							\State $p \gets a[Town] / a_{total}$
							\If{$rnd \leq p$}
								\State $NextTown \gets Town$
								\State \textbf{break}
							\EndIf
							\State $rnd \gets rnd - p$
						\EndFor
					\EndIf
					\State add $(ActualTown,NextTown)$ to $VisitedEdges$
					\State add $NextTown$ to $VisitedTowns$
					\State $L \gets L + \delta[ActualTown,NextTown]$
					\State $\tau[ActualTown,NextTown] \gets (1-\rho_{local}) \cdot \tau[ActualTown,NextTown]$ \\
					\hskip2\algorithmicindent\relax	$ + \rho_{local} \cdot \tau_0$
					\State $\tau[NextTown,ActualTown] \gets \tau[ActualTown,NextTown]$
					\State \Comment Die letzte Zeile gilt nur für symmetrische TSP!
					\State $ActualTown \gets NextTown$
				\EndWhile
				\State $NextTown \gets StartingTown[Ant]$
				\State add $(ActualTown,NextTown)$ to $VisitedEdges$
				\State $L \gets L + \delta[ActualTown,NextTown]$
				\State $\tau[ActualTown,NextTown] \gets (1-\rho_{local}) \cdot \tau[ActualTown,NextTown]$ \\
				\hskip2\algorithmicindent\relax	$ + \rho_{local} \cdot \tau_0$
				\State $\tau[NextTown,ActualTown] \gets \tau[ActualTown,NextTown]$
				\State \Comment Die letzte Zeile gilt nur für symmetrische TSP!
				\If{$L < L_{min}$}
					\State $L_{min} \gets L$
					\State $ShortestTour \gets VisitedEdges$
				\EndIf
			\EndFor
			\For{$\forall (i,j), i \in Towns, j \in Towns$}
				\State $\tau[i,j] \gets (1-\rho) \cdot \tau[i,j]$
				\If{$(i,j) \in ShortestTour$}
					\State $\tau[i,j] \gets \rho \cdot \tau_0$
				\EndIf
				\If{$(j,i) \in ShortestTour$} \Comment Gilt nur für symmetrische TSP!
					\State $\tau[i,j] \gets \rho \cdot \tau_0$
				\EndIf
			\EndFor
		\EndWhile
		\State \textbf{return} $ShortestTour$
	\EndFunction
	\end{algorithmic}
\end{algorithm}
\vfill

\clearpage
\section{Ant-Q}\label{appendix:AQ}

\begin{algorithm}[!h]
  \caption{Ant-Q Umsetzung des TSP}
	\begin{algorithmic}
	\Function{AntSystem}{$Towns, \delta, n_{Ants}, i_{max}, \tau_{0}, q_0, \alpha, \beta, \rho_{global}, \rho_{lokal}$}
		\State $i \gets 0$ \Comment Initialisierung
		\State $ShortestTour \gets \text{empty Set of Edges}$
		\State $L_{min} \gets \infty$
		\State $\tau \gets \text{Array of Floating Point Numbers}$
		\For{$\forall (i,j), i \in Towns, j \in Towns$}
			\State $\tau[i,j] \gets \tau_{0}$
		\EndFor
		\While{$i < i_{max}$} \Comment Die Hauptschleife
			\State $i \gets i+1$
			\State $StartingTown \gets \text{Array}[n_{Ants}]\text{ of Towns}$
			\State \textbf{shuffle} $Towns$ \Comment Verteile die Ameisen zufällig auf verschiedene Städte
			\For{$Ant \gets 1\dots{}n_{Ants}$}
				\State $StartingTown[Ant] \gets Towns[Ant \mod length(Towns)]$
			\EndFor
			\For{$Ant \gets 1\dots{}n_{Ants}$} \Comment Berechne eine Tour für jede Ameise
				\State $VisitedTowns \gets \text{empty Set of Towns}$
				\State $VisitedEdges \gets \text{empty Set of Edges}$
				\State $ActualTown \gets StartingTown[Ant]$
				\State add $StartingTown[Ant]$ to $VisitedTowns$
				\State $L \gets 0$
				\While{$\exists Town, Town \in Towns \setminus VisitedTowns$}
					\State $rnd \gets Random(0,1)$ \Comment Wähle die nächste Stadt
					\State $a_{total} \gets 0$ \Comment Berechne die Attraktivität aller möglichen Kanten
					\State $a \gets \text{Array of Floating Point Number}$  
					\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
						\State $a[Town] \gets [\tau(ActualTown,Town)] ^ \alpha \cdot [\delta(ActualTown,Town)] ^ \beta$
						\State $a_{total} \gets a_{total} + a[Town]$
					\EndFor
					\State $NextTown \gets NULL$
					\If{$rnd \leq q_0$} \Comment Fall 1: Wähle die beste Kante
						\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
							\If{$a(ActualTown,Town) < \delta(ActualTown,NextTown)$}
								\State $NextTown \gets Town$ 
							\EndIf
						\EndFor
					\algstore{alg:ACS}
	\end{algorithmic}
\end{algorithm}
\vfill

\begin{algorithm}[!h]
  \ContinuedFloat
  \caption{Ant-Q Umsetzung des TSP (2.Teil)}
	\begin{algorithmic}
					\algrestore{alg:ACS}
					\Else \Comment Fall 2: Wähle zufällig zwischen den Kanten
						\State $rnd \gets (rnd - q_0) / (1 - q_0)$
						\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
							\State $p \gets a[Town] / a_{total}$
							\If{$rnd \leq p$}
								\State $NextTown \gets Town$
								\State \textbf{break}
							\EndIf
							\State $rnd \gets rnd - p$
						\EndFor
					\EndIf
					\State add $(ActualTown,NextTown)$ to $VisitedEdges$
					\State add $NextTown$ to $VisitedTowns$
					\State $L \gets L + \delta[ActualTown,NextTown]$
					\State $\tau[ActualTown,NextTown] \gets (1-\rho_{local}) \cdot \tau[ActualTown,NextTown]$ \\
					\hskip2\algorithmicindent\relax	$ + \rho_{local} \cdot \tau_0$
					\State $\tau[NextTown,ActualTown] \gets \tau[ActualTown,NextTown]$
					\State \Comment Die letzte Zeile gilt nur für symmetrische TSP!
					\State $ActualTown \gets NextTown$
				\EndWhile
				\State $NextTown \gets StartingTown[Ant]$
				\State add $(ActualTown,NextTown)$ to $VisitedEdges$
				\State $L \gets L + \delta[ActualTown,NextTown]$
				\State $\tau[ActualTown,NextTown] \gets (1-\rho_{local}) \cdot \tau[ActualTown,NextTown]$
				\State $\Delta\tau \gets 0$
				\For{$\forall Town, Town \in Towns \setminus VisitedTowns$}
					\If{$\Delta\tau < \tau[NextTown,Town]$}
						\State $\Delta\tau \gets \tau[NextTown,Town]$
					\EndIf
				\EndFor
				\State $\tau[NextTown,ActualTown] \gets \tau[ActualTown,NextTown] + \rho_{local} \cdot \Delta\tau$
				\State \Comment Die letzte Zeile gilt nur für symmetrische TSP!
				\If{$L < L_{min}$}
					\State $L_{min} \gets L$
					\State $ShortestTour \gets VisitedEdges$
				\EndIf
			\EndFor
			\For{$\forall (i,j), i \in Towns, j \in Towns$}
				\State $\tau[i,j] \gets (1-\rho) \cdot \tau[i,j]$
				\If{$(i,j) \in ShortestTour$}
					\State $\tau[i,j] \gets \rho \cdot \tau_0$
				\EndIf
				\If{$(j,i) \in ShortestTour$} \Comment Gilt nur für symmetrische TSP!
					\State $\tau[i,j] \gets \rho \cdot \tau_0$
				\EndIf
			\EndFor
		\EndWhile
		\State \textbf{return} $ShortestTour$
	\EndFunction
	\end{algorithmic}
\end{algorithm}
\vfill

\end{appendix}
\end{document}
